package leetcode.editor.cn.dsa16_bfsdfs;
//翻转一棵二叉树。
//
// 示例：
// 输入：
//      4
//   /   \
//  2     7
// / \   / \
//1   3 6   9 
// 输出：
//
//      4
//   /   \
//  7     2
// / \   / \
//9   6 3   1 
//
// 备注: 
// 这个问题是受到 Max Howell 的 原问题 启发的 ：
// 谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
// Related Topics 树 
// 👍 712 👎 0

public class InvertBinaryTree226 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public TreeNode invertTree(TreeNode root) {
            // 1.递归结束条件
            if (root == null) return root; // 空树不需要交换
            // 2.函数的主功能：交换当前节点的左右子树
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
            // 等价关系式：翻转一棵二叉树 = 翻转二叉树的左子树 && 翻转二叉树的右子树
            // 递归处理左子树交换
            invertTree(root.left);
            // 递归处理右子树交换
            invertTree(root.right);
            return root;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}